package practice_2025_8_31;

class Solution {
    boolean[][] row = new boolean[9][10];
    boolean[][] col = new boolean[9][10];
    boolean[][][] grid = new boolean[3][3][10];
    public void solveSudoku(char[][] board) {
        //初始化
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                if(board[i][j] != '.'){
                    int index = board[i][j] - '0';
                    //判断是否出现过
                    // if(row[i][index] || col[j][index] || grid[i / 3][j / 3][index]){
                    //     return false;
                    // }
                    row[i][index] = true;
                    col[j][index] = true;
                    grid[i / 3][j / 3][index] = true;
                }
            }
        }
        // 填入
        dfs(board);

    }
    public boolean dfs(char[][] board){
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                //出现未填的数
                if(board[i][j] == '.'){
                    //尝试填数
                    for(int k = 1; k <= 9; k++){
                        if(row[i][k] || col[j][k] || grid[i / 3][j / 3][k]){
                            continue;
                        }else{
                            char ch = (char)(k + '0');
                            board[i][j] = ch;
                            row[i][k] = true;
                            col[j][k] = true;
                            grid[i / 3][j / 3][k] = true;
                            boolean ret = dfs(board);
                            //回溯
                            if(ret == false){
                                board[i][j] = '.';
                                row[i][k] = false;
                                col[j][k] = false;
                                grid[i / 3][j / 3][k] = false;
                            }else{
                                return true;
                            }
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
}